Human beings often write computer programs in a "high level language," such as C. Computer programs (called "source programs") written in a high level language must be converted into instructions understandable by a computer. This process is called "compiling" the program and is performed by a software program called a "compiler." Thus, a compiler compiles a source program (written in a high level language) into an "object" program, which contains instructions executable by the computer.
Source programs can be thought of as being divided into "logical" blocks. Each block contains one or more statements in the source program. Conventional compilers often rearrange the order of blocks to make execution of the resulting object program more efficient.
Some conventional compilers produce object programs that execute inefficiently. An example of a source program that is often compiled to execute inefficiently is a source program containing a "branch" instruction, such as an "if-then-else" statement. Inefficiencies result when the compiler compiles an "if-then-else" statement in such a way that the computer executing the compiled branch instruction frequently has to transfer execution to a different location in the program. In contrast, a more efficient compilation generates an object program where the computer executing the compiled branch instruction usually "falls through" the branch instruction without having to transfer execution to a different part of the program. Unfortunately, rearranging the blocks of a computer program has some constraints, since making one block a fall-through prevents other blocks from being fall throughs.
What is needed is a compiler that generates an object program that causes more "fall throughs" and fewer branches during execution.